
If we define $\alpha=\min{(|\lambda_1|,|\lambda_{n-1}|)}$, then the
following theorems hold,

\begin{theorem}(\emph{Expander Mixing Lemma})
Let $G$ be an $d$-regular graph, $S,T\subseteq V$, $E(S,T)$ denotes
the edges between the sets $S$ and $T$,
\begin{eqnarray*}
\left|{|S||T|\over n^2}-{E(S,T)\over dn}\right|\le 1-\alpha
\end{eqnarray*}
\end{theorem}

and further, if we denote $B\subset V$ is a set of vertices with
density $\beta={|B|\over|V|}$. Choose $X_0\in V$ uniformly at
random, and let $X_0,\dots,X_t$ be a random walk starting at $X_0$.
Denote by $(B,t)$ the event that the $X_i\in B$, for $\forall i,
0\le i\le t$.

\begin{theorem}
\begin{eqnarray*}
Pr[(B,t)]\le(\beta+1-\alpha)^t
\end{eqnarray*}
\end{theorem}

The inequality above can be thought of in the sense that, if the
underlying graph has good expansion property, and the density of bad
vertices is relatively small, then with high probability, the random
walk will hit some good vertices. And if keep walking, with high
probability, a majority of the vertices visited must be ``good''.

Now consider a BPP style problem, namely, given an instance $x$, if
it is ``good'', then it is accepted with probability greater than
$9\over 10$; if it is not ``good'', it is accepted with probability
no more than $1\over 10$.

A straightforward method to solve this problem is to repeat picking
vertices uniform randomly for $t$ times, which can reduce the error
rate to ${1\over 10^t}$. Suppose each trial requires $m$ coin
tosses, then this algorithm requires totally $m\cdot t$ coins.

Another choice is to think of an $d$-regular expander, such that
$V=\{0,1\}^m$ representing the domain of all the possible coin
tosses. Now first toss $m$ coins to determine where to start, and
then toss $\log{d}$ coins for $t$ times to determine the path of a
random walk, and finally return the majority of the outputs on these
inputs. By assuming $(\beta+1-\alpha)$ is small enough, one may
deduce an exponentially small error bound. This algorithm uses
totally $m+\log{d}\cdot t=m+O(t)$ coin tosses.

As one may observe above that, the main purpose of utilizing random
walks on expanders is to reduce the requirement of random bits.
